package algorithm.middle;

import com.sun.xml.internal.bind.v2.model.core.ID;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: NthUglyNumber264
 * @description: 编写一个程序，找出第 n 个丑数。
 * <p>
 * 丑数就是质因数只包含 2, 3, 5 的正整数。
 * @date 2020/8/2816:45
 * @since V1.0
 */
public class NthUglyNumber264 {
    public static void main(String[] args) {
        //int i = nthUglyNumber(1352);
        System.out.println(isUgly(1));
    }

    public static int nthUglyNumber(int n) {
        int[] arr = new int[n];
        arr[0] = 1;
        int a = 0;
        int b = 0;
        int c = 0;
        for (int i=1;i<n;i++){
            int min = Math.min(Math.min(arr[a] * 2, arr[b] * 3), arr[c] * 5);
            arr[i] = min;
            if (min == arr[a] * 2) a++;
            if (min == arr[b] * 3) b++;
            if (min == arr[c] * 5) c++;
        }
        return arr[n-1];
    }

    //小顶堆 优先队列
    //因为heap会进行保证堆顶最小，int溢出以后变成负数会导致结果偏差，1690能保证结果是int，但是过程中会往heap里面塞2*n的数字
    public static int fun(int n) {
        int[] arr = new int[n];
        HashSet<Long> set = new HashSet<>();
        PriorityQueue<Long> que = new PriorityQueue<>();
        set.add(1l);
        que.add(1l);
        long a=0,b=0,c=0;
        for (int i=0;i<n;i++){
            long poll = que.poll();
            arr[i] = (int) poll;
            a=poll*2;
            b=poll*3;
            c=poll*5;
            if(!set.contains(a)){
                que.add(a);
                set.add(a);
            }
            if(!set.contains(b)){
                que.add(b);
                set.add(b);
            }
            if(!set.contains(c)){
                que.add(c);
                set.add(c);
            }
        }
        return arr[n-1];
    }



    public static boolean isUgly(int n) {
        if (n<=0) return false;
        while (n%2==0){
            n=n/2;
        }
        while (n%3==0){
            n=n/3;
        }
        while (n%5==0){
            n=n/5;
        }
        return n==1;
    }

    public int nthUglyNumber3(int n) {
        PriorityQueue<Long> que = new PriorityQueue<>(Comparator.comparing((o)->o));
        int i=0;
        que.add(1l);
        while (i<n){
            long poll = que.poll();
            long a = poll*2;
            long b = poll*3;
            long c = poll*5;
            if (!que.contains(a)) que.add(a);
            if (!que.contains(b)) que.add(b);
            if (!que.contains(c)) que.add(c);
            i++;
        }
        long poll = que.poll();
        int m = (int) poll;
        return m;
    }
}
